package it.uniroma3.dia.digraph.algorithm.utility;

import java.awt.Point;
import java.awt.geom.Point2D;
import java.util.Collection;
import java.util.List;
import java.util.Map;

import org.graphdrawing.graphml.xmlns.EdgeType;
import org.graphdrawing.graphml.xmlns.NodeType;

class Triangle {
	
	/**
	 * Returns a point representing the circumcenter for the specified triangle.
	 * http://en.wikipedia.org/wiki/Circumscribed_circle#Cartesian_coordinates
	 * @param xa
	 * @param ya
	 * @param xb
	 * @param yb
	 * @param xc
	 * @param yc
	 * @return
	 */
	public static Point2D.Double getCircumCenter(double xa, double ya,
			double xb, double yb, double xc, double yc){
		Point2D.Double point = new Point2D.Double();
		double x, y;
		double d = 2*(xa*(yb-yc) + xb*(yc-ya)+xc*(ya-yb));
		
		x = (	(ya*ya + xa*xa)*(yb-yc) +
				(yb*yb + xb*xb)*(yc-ya) +
				(yc*yc + xc*xc)*(ya-yb))/d;
		
		y = (	(ya*ya + xa*xa)*(xc-xb) +
				(yb*yb + xb*xb)*(xa-xc) +
				(yc*yc + xc*xc)*(xb-xa))/d;
		
		
		point.setLocation(x, y);
		
		return point;
	}
	
	public static Point2D.Double getIsoscelesCircumCenter(Point2D.Double baseMid, double theta, NodeType baseVertex, Point2D.Double topVertex){
		double a, h, z;
		double[] centerCoords;
		
		h = Utility.distance(baseMid, topVertex);
		a = Utility.distance(baseVertex, baseMid);		
		
		z = (a*a - h*h)/(2*h);
		
		centerCoords = Utility.convertToCartesianCoords(baseMid, (theta+180)%360, z);
		return new Point2D.Double(centerCoords[0], centerCoords[1]);
	}

	/**
	 * Calculates the value of the area of triangle ABC
	 * @param xa vertex A x coord
	 * @param ya vertex A y coord
	 * @param xb vertex B x coord
	 * @param yb vertex B y coord
	 * @param xc vertex C x coord
	 * @param yc vertex C y coord
	 * @return the value of the area of triangle ABC
	 */
	public static double calculateArea(double xa, double ya, double xb, double yb, double xc, double yc){
		return Math.abs(signedArea(xa, ya, xb, yb, xc, yc));		
	}

	/**
	 * Calculates the <b>signed</b> value of the area of triangle ABC
	 * @param xa vertex A x coord
	 * @param ya vertex A y coord
	 * @param xb vertex B x coord
	 * @param yb vertex B y coord
	 * @param xc vertex C x coord
	 * @param yc vertex C y coord
	 * @return the <b>signed</b> value of the area of triangle ABC
	 */
	public static double signedArea(double xa, double ya, double xb, double yb, double xc, double yc){
		return 0.5 * Matrix.det(1, 1, 1, xa, xb, xc, ya, yb, yc);
	}


	/**
	 * Checks whether point P lies in triangle ABC
	 * @param px point P x coord
	 * @param py point P y coord
	 * @param xa vertex A x coord
	 * @param ya vertex A y coord
	 * @param xb vertex B x coord
	 * @param yb vertex B y coord
	 * @param xc vertex C x coord
	 * @param yc vertex C y coord
	 * @return true if P lies in ABC, false otherwhise
	 */
	public static boolean pointInTriangle(double px, double py, 
			double xa, double ya, double xb, double yb, double xc, double yc){
		double lambdaA, lambdaB, lambdaC;
		double triangleArea = calculateArea(xa, ya, xb, yb, xc, yc);
		lambdaA = signedArea(px, py, xb, yb, xc, yc)/triangleArea;
		lambdaB = signedArea(xa, ya, px, py, xc, yc)/triangleArea;
		lambdaC = signedArea(xa, ya, xb, yb, px, py)/triangleArea;		

		if (lambdaA>0 && lambdaB>0 && lambdaC>0 && lambdaA+lambdaB+lambdaC==1){
			System.out.print("point ("+px+" "+py+") in triangle: a:"+xa+","+ya+" b:"+xb+","+yb+" c:"+xc+","+yc);
			System.out.println(":\tupdate triangle");			
			return true;
		}
		return false;
	}
	
	public static double[] barycentricCoords(double px, double py, double xa,
			double ya, double xb, double yb, double xc, double yc) {
		double lambdaA, lambdaB, lambdaC;
		double triangleArea = calculateArea(xa, ya, xb, yb, xc, yc);
		
		lambdaA = calculateArea(px, py, xb, yb, xc, yc)/triangleArea;
		lambdaB = calculateArea(xa, ya, px, py, xc, yc)/triangleArea;
		lambdaC = calculateArea(xa, ya, xb, yb, px, py)/triangleArea;	
		
		return new double[]{lambdaA, lambdaB, lambdaC};
	}

	/**
	 * Checks whether a triangle intersects a line
	 * @param lx1 line startpoint x coord
	 * @param ly1 line startpoint y coord
	 * @param lx2 line endpoint x coord
	 * @param ly2 line endpoint y coord
	 * @param xa vertex A x coord
	 * @param ya vertex A y coord
	 * @param xb vertex B x coord
	 * @param yb vertex B y coord
	 * @param xc vertex C x coord
	 * @param yc vertex C y coord
	 * @return true if any edge intersects the line, false otherwise
	 */
	public static boolean intersectLine(double lx1, double ly1, double lx2, double ly2, 
			double xa, double ya, double xb, double yb, double xc, double yc){
		return intersectLine(false, lx1, ly1, lx2, ly2, xa, ya, xb, yb, xc, yc);
	}

	/**
	 * Checks whether a triangle intersects a line
	 * @param excludeAB if true, does not perform check on edge AB
	 * @param lx1 line startpoint x coord
	 * @param ly1 line startpoint y coord
	 * @param lx2 line endpoint x coord
	 * @param ly2 line endpoint y coord
	 * @param xa vertex A x coord
	 * @param ya vertex A y coord
	 * @param xb vertex B x coord
	 * @param yb vertex B y coord
	 * @param xc vertex C x coord
	 * @param yc vertex C y coord
	 * @return true if any edge intersects the line, false otherwise
	 */
	public static boolean intersectLine(boolean excludeAB, double lx1, double ly1, double lx2, double ly2, 
			double xa, double ya, double xb, double yb, double xc, double yc){

		boolean result = false;
		Point i = new Point();
		Point j = new Point();
		Point l1 = new Point();
		Point l2 = new Point();
		l1.setLocation(lx1, ly1);
		l2.setLocation(lx2, ly2);		

		//check AB
		if (!excludeAB){ //can be useful in some cases
			i.setLocation(xa, ya);
			j.setLocation(xb, yb);
			result = Utility.existsIntersection(l1, l1, i, j);
		}		
		//check AC
		if (!result){
			i.setLocation(xa, ya);
			j.setLocation(xc, yc);
			result = Utility.existsIntersection(l1, l1, i, j);
		}		
		//check BC
		if (!result){
			i.setLocation(xb, yb);
			j.setLocation(xc, yc);
			result = Utility.existsIntersection(l1, l1, i, j);
		}			
		return result;
	}

	/**
	 * Checks whether triangle ABC is disjoint from the given {@link Collection} of elements
	 * @param a vertex A
	 * @param b vertex B
	 * @param c vertex C
	 * @param id2nodes a {@link Map} <id, Node>
	 * @param edges a Collection of {@link EdgeType}
	 * @return true if AC or BC intersects the line, false otherwise
	 */
	public static boolean isDisjoint(Point a, Point b, Point c, Map<String,NodeType> id2nodes, List<EdgeType> edges){
		boolean result = false;

		//check for nodes
//		for (NodeType n : id2nodes.values())
//			result = result || pointInTriangle(n.getX(), n.getY(), a.getX(), a.getY(), b.getX(), b.getY(), c.getX(), c.getY());
		
		result = result || contains(a, b, c, id2nodes.values());
		
		
		if(!result){
			//check intersection with edges
			double lx1, ly1, lx2, ly2;
			for (EdgeType e : edges){
				try {
					lx1 = id2nodes.get(e.getSource()).getX();
					ly1 = id2nodes.get(e.getSource()).getY();
					lx2 = id2nodes.get(e.getTarget()).getX();
					ly2 = id2nodes.get(e.getTarget()).getY();

					result = result || intersectLine(lx1, ly1, lx2, ly2, a.getX(), a.getY(), b.getX(), b.getY(), c.getX(), c.getY());
				} catch (NullPointerException exc) {

					// one of the nodes has been removed from id2nodes
					// so that node has not to be checked
					// so, none of incident edges on that node should be checked
				}
			}
		}
		
		

		return !result;
	}
	
	
	public static boolean contains(Point2D a, Point2D b, Point2D c, Collection<NodeType> nodes){
		boolean result = false;
		for (NodeType n : nodes){
			result = result || pointInTriangle(n.getX(), n.getY(), a.getX(), a.getY(), b.getX(), b.getY(), c.getX(), c.getY());
		}
		return result;
	}


	public static boolean isTspannable(NodeType source, NodeType current,
			Point2D triangleVertex, List<EdgeType> edges, List<NodeType> nodes, Map<String, NodeType> id2nodes) {
		boolean result = true;

		//point in polygon
		for(int i = nodes.indexOf(current)+1; i<nodes.size();i++){
			result &= ! pointInTriangle(nodes.get(i).getX(), nodes.get(i).getY(), 
					source.getX(), source.getY(), current.getX(), current.getY(), triangleVertex.getX(), triangleVertex.getY());
		}	

		//check for edges
		if (result){
			NodeType s, t;
			for(EdgeType edge : edges){
				s = id2nodes.get(edge.getSource());
				t = id2nodes.get(edge.getTarget());
				// the edge should not incide on any of the vertices from source to current
				if (nodes.indexOf(s)>nodes.indexOf(current) && nodes.indexOf(t)>nodes.indexOf(current)){

					result &= !Utility.intersection(s, t, source, current);
					result &= !Utility.intersection(s, t, source, triangleVertex);
					result &= !Utility.intersection(s, t, current, triangleVertex);
				}
			}

		}
		return result;
	}

	
}
